package org.guass.sequence;

import java.util.Arrays;

/**
 * 顺序表的实现
 * @author guass
 * @date 2022年03月11日 10:43
 */
public class SeqList<T> implements LinearList{

    private T[] data;  //存放数组

    //最大容量
    private int maxSize;

    /**
     * 当前已存表项的最后位置(从0开始)
     */
    private int last;

    SeqList(int maxSize){
        this.maxSize = maxSize;
        last = -1;
        data = (T[]) new Object[maxSize];
    }

    private void resize(int newSize){
        if (newSize > maxSize) {

            T[] newArray = (T[]) new Object[newSize];

            int n = last + 1;
            T[] srcPtr = data;
            T[] destPtr = newArray;

            int index = 0;
            while (n-- > 0){
                destPtr[index++] = srcPtr[index++];
            }

            data = newArray;
            maxSize = newSize;
        }
    }

    @Override
    public int size() {
        return maxSize;
    }

    @Override
    public int length() {
        return last + 1;
    }

    @Override
    public <T> int search(T t) {
        for (int i = 0; i <= last; i++) {
            if (data[i].equals(t)) {
                return i;
            }
        }
        return -1;
    }


    @Override
    public <T> T getData(int index) {
        if(index < 0 || index >= maxSize)
        {
            return null;
        }
        return (T) data[index];
    }

    @Override
    public  void setData(int index, Object t) {
        data[index] = (T) t;
    }

    @Override
    public  boolean insert(int index, Object x) {

        //将新元素x插入到表第index(0<= index <= last + 1) 之后，
        //index = 0是虚拟的 ，实际上是插入到第1个元素的位置

        //表满
        if (last == maxSize -1) {
            return false;
        }

        //参数不合理
        if(index < 0 || index > last + 1 )
        {
            return false;
        }

        //以此后移 ，空出第index号位置
        for (int j = last; j >= index ; j--) {
            data[j+1] = data[j];
        }

        //插入
        data[index] = (T) x;

        //最后位置+1
        last++;

        //成功
        return true;
    }

    @Override
    public <T> T remove(int index) {
        //删除第index(last+1 >= index >= 1 )

        //没元素可删除
        if (last == -1) {
            return null;
        }

        if(index < 1 || index > last + 1){
            return null;
        }

        //取值
        T t = (T) data[index - 1];

        //以此前移
        for (int j = index; j <= last  ; j++) {
            data[j-1] = data[j];
            if (j == last) {
                data[j] = null;
            }
        }

        last--;
        return  t;
    }

    @Override
    public boolean isEmpty() {
        return last == -1;
    }

    @Override
    public boolean isFull() {
        return (last + 1) == maxSize;
    }

    @Override
    public void sort() {

    }

    @Override
    public void union(LinearList la, LinearList lb) {
        //合并顺序表存于la ，重复元素只留一个
        int n = la.length();
        int m = lb.length();
        int k;
        T x;

        for (int i = 0; i < m; i++) {
            // TODO: 2022/3/11 在lb中取一元素 
            x = lb.getData(i);
            // TODO: 2022/3/11 在la中搜索
            k = la.search(x);

            // TODO: 2022/3/11 未找到则插入
            if (k == -1) {
                la.insert(n,x);
                n++;
            }
        }
    }

    @Override
    public void intersection(LinearList la, LinearList lb) {
        //求两个表共有元素存于la
        int n = la.length();
        int m = lb.length();
        int k;
        int i = 1;
        T x;

        while (i <= n){
            x = la.getData(i); //la中取一元素
            k = lb.search(x); //lb中查找

            if (k == -1) {
                la.remove(i);
                n--;
            }else {
                i++;
            }
        }
    }

    @Override
    public String toString() {
        return "SeqList{" +
                "data=" + Arrays.toString(data) +
                ", maxSize=" + maxSize +
                ", last=" + last +
                '}';
    }
}
